#include <iostream>
#include <string.h>
#include <assert.h>

namespace wangshu
{
    class string
    {
    public:
        typedef char* iterator;
        typedef const char* const_iterator; 
        
        string(const char* str = ""):
            _size(strlen(str)), _capacity(_size)
        {
            _str = new char(_size);
            strcpy(_str, str);
        }

        string(const string& str)
        {
            _size = str._size;
            _capacity = str._capacity;
            _str = new char(_size);
            strcpy(_str, str._str);
        }

        iterator begin()
        {
            return _str;
        }

        iterator end()
        {
            return _str + _size;
        }
        
        const_iterator begin() const
        {
            return _str;
        }

        const_iterator end() const
        {
            return _str + _size;
        }

        void reserve(int n)
        {
            if(n > _capacity) // 扩容的逻辑
            {
                char* tmp = new char[n + 1];
                strcpy(tmp, _str);
                delete [] _str;
                _str = tmp;
                _capacity = n;
            }
        }
        void push_back(char ch)
        {
            if(_size == _capacity)
            {
                reserve(_capacity == 0 ? 4 : 2 * _capacity);
            }
            _str[_size] = ch;
            _size++;
            _str[_size] = '\0';
        }
        void append(const char* str)
        {
            int len = strlen(str);
            if(_size + len > _capacity)
            {
                reserve(_size + len);
            }
            strcpy(_str + _size, str);
            _size += len;
        }
        
        void insert(size_t pos, char ch)
        {
            assert(pos <= _size);
            if(_size == _capacity)
            {
                reserve(_capacity == 0 ? 4 : 2 * _capacity);
            }
            int end = _size + 1;
            while(end > pos)
            {
                _str[end] = _str[end - 1];
                end--;
            }
            _str[end] = ch;
            _size++;
        }
        
        void insert(size_t pos, const char* str)
        {
            assert(pos <= _size);
            int len = strlen(str);
            if(_size + len > _capacity)
            {
                reserve(_size + len);
            }
            int end = _size + len;
            while(end > pos)
            {
                _str[end] = _str[end - len];
                end--;
            }
            strncpy(_str, str, len); // '\0'不拷贝
            _size += len;
        }

        char* c_str()
        {
            return _str;
        }
        size_t size()
        {
            return _size;
        }
        size_t capacity()
        {
            return _capacity;
        }
        
        void clear()
        {
            _str[0] = '\0';
            _size = 0;
        }
        
        void resize(size_t size, char ch = '\0')
        {
            if(size < _size)
            {
                _str[size] = '\0';
                _size = size;
            }
            else
            {
                reserve(size);
                while(_size <= size)
                {
                    _str[_size] = ch;
                    _size++;
                }
            }
            _str[_size] = '\0';
        }

        string substr(size_t pos, size_t len = npos)
        {
            assert(pos < _size);
            string s;
            int end = pos + len;
            if(len == npos || end >= _size)
            {
                len = _size - pos;
                end = _size;
            }
            s.reserve(len);
            for(size_t i = pos; i < end; i++)
            {
                s += _str[i];
            }
            return s;
        }

        void erase(size_t pos, size_t len = npos)
        {
            if(len == npos || pos + len > _size)
            {
                _str[pos] = '\0';
                _size = pos;
            }
            else
            {
                int begin = pos + len;
                while(begin < _size)
                {
                    _str[begin - len] = _str[begin];
                    begin++;
                }
                _size -= len;
            }
        }

        string& operator+=(char ch)
        {
            push_back(ch);
            return *this;
        }

        string& operator+=(const char* s)
        {
            append(s);
            return *this;
        }

        bool operator<(const string& s) const
        {
            return strcmp(_str, s._str) < 0;
        }

        bool operator==(const string& s) const
        {
            return strcmp(_str, s._str) == 0;
        }

        bool operator<=(const string& s) const
        {
            return *this < s || *this == s;
        }
        
        bool operator>(const string& s) const
        {
            return !(*this <= s);
        }
        
        bool operator>=(const string& s) const
        {
            return *this > s || *this == s;
        }

        char operator[](size_t pos)
        {
            return _str[pos];
        }

    private:
        const static size_t npos;
        char* _str;
        size_t _size;
        size_t _capacity;
    };
    const size_t wangshu::string::npos= -1;

    std::ostream& operator<<(std::ostream& os, const string& s)
    {
        for(auto& ch : s)
        {
            os << ch;
        }
        return os;
    }
    std::istream& operator>>(std::istream& is, string& s)
    {
        s.clear();

        size_t i = 0;
        char buffer[128], ch;
        ch = is.get();
        while(ch != ' ' && ch != '\n')
        {
            buffer[i++] = ch;
            if(i == 128)
            {
                buffer[i] = '\0';
                s += buffer;
                i = 0;
            }
            ch = is.get();
        }
        if(i != 0)
        {
            buffer[i] = '\0';
            s += buffer;
        }
        return is;
    }
}